package leetcode.p876;

import leetcode.ListNode;

public class Solution {
    public ListNode middleNode2(ListNode head) {
        //方法二：通过两个引用，快引用走两步，慢引用走一步，快的为空，慢的在中间
        ListNode fast=head;
        ListNode slow=head;

        while (fast!=null) {
            fast=fast.next;
            if(fast==null) {
                break;
            }
            fast=fast.next;
            slow=slow.next;
        }
        return slow;

    }


    public ListNode middleNode(ListNode head) {
        //返回链表的中间结点
        int n=getCount(head);//中间结点为第n个数
        int step=n/2+1;//到中间结点需要走一步

        ListNode ans=head;
        for(int i=0;i<step-1;i++) {
            ans=ans.next;
        }
        return ans;
    }

    private int getCount(ListNode head) {
        int count=0;
        for(ListNode cur=head;cur!=null;cur=cur.next) {
            count++;
        }
        return count;
    }
}
